package com.pan.alg.niuke.link;


import java.util.HashMap;
import java.util.Map;

/**
 * 描述
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 *
 * 数据范围： n\le10000n≤10000，1<=结点值<=100001<=结点值<=10000
 * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
 *
 * 例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
 *
 * 可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
 * 输入描述：
 * 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
 * 返回值描述：
 * 返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
 */
public class LinkCircleEntrance{

    public static void main(String[] args) {
        ListNode listNode= new ListNode(-1);
        //1、判断是否有环
        boolean hasCycle = LinkHasCircle.hasCycle(listNode);

        //2、判断哪个节点有两个不同的指针指向它
        if(hasCycle){
            //获取入口节点
            ListNode listNode1 = getCircleEntrance(listNode);
        }


    }

    public static ListNode getCircleEntrance(ListNode listNode){
        Map<ListNode,Integer> nextNodeCounter = new HashMap<>();
        while(listNode!=null){
            if(nextNodeCounter.containsKey(listNode)){
                return listNode;
            }else{
                nextNodeCounter.put(listNode,1);
            }
            listNode = listNode.next;
        }
        return null;
    }


}
